/*
 * @lc app=leetcode.cn id=160 lang=javascript
 *
 * [160] 相交链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */

/**
 * map映射
 */
var getIntersectionNode = function(headA, headB) {
  if(!headA || !headB) return null;
  let map = new Map();
  let p = headA;
  while(p) {
    map.set(p, 1);
    p = p.next;
  }
  p = headB
  while(p) {
    if(map.get(p)) return p;
    p = p.next;
  }
  return null;
};

// 双指针
/**
 * 方法二：双指针
思路和算法
s使用双指针的方法，可以将空间复杂度降至 O(1)O(1)。
只有当链表 \textit{headA}headA 和 \textit{headB}headB 都不为空时，两个链表才可能相交。因此首先判断链表 \textit{headA}headA 和 \textit{headB}headB 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 \text{null}null。
当链表 \textit{headA}headA 和 \textit{headB}headB 都不为空时，创建两个指针 \textit{pA}pA 和 \textit{pB}pB，初始时分别指向两个链表的头节点 \textit{headA}headA 和 \textit{headB}headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：
每步操作需要同时更新指针 \textit{pA}pA 和 \textit{pB}pB。
如果指针 \textit{pA}pA 不为空，则将指针 \textit{pA}pA 移到下一个节点；如果指针 \textit{pB}pB 不为空，则将指针 \textit{pB}pB 移到下一个节点。
如果指针 \textit{pA}pA 为空，则将指针 \textit{pA}pA 移到链表 \textit{headB}headB 的头节点；如果指针 \textit{pB}pB 为空，则将指针 \textit{pB}pB 移到链表 \textit{headA}headA 的头节点。
当指针 \textit{pA}pA 和 \textit{pB}pB 指向同一个节点或者都为空时，返回它们指向的节点或者 \text{null}null。
*/
// @lc code=end

